#ifndef DIVIDE_H
#define	DIVIDE_H

#include "list.h"
#include "utils.h"
#include "compare.h"
#include "add.h"
#include "multiply.h"

template<typename Num, int value, int carry>
struct DivideByShort_
{
   typedef typename DivideByShort_<List<Num::data + carry,
           typename Num::tail>, value, 0 >::result result;
};

template<typename Num, int value>
struct DivideByShort_<Num, value, 0>
{
   typedef List<Num::data / value,
           typename DivideByShort_<typename Num::tail, value,
           (Num::data % value) * 10 >::result > result;
};

template<int value, int carry>
struct DivideByShort_<EmptyList, value, carry>
{
   typedef EmptyList result;
};

template<int value>
struct DivideByShort_<EmptyList, value, 0>
{
   typedef EmptyList result;
};

template<typename Num, int value>
struct DivideByShort
{
   typedef typename CutZeroes<typename DivideByShort_<Num, value,
           0>::result >::result result;
};

template<typename Num1, typename Num2,
        typename Left, typename Right, typename Middle>
struct DivideBinSearch
{
   typedef typename MetaIf<(Compare<Num1,
           typename Multiply<Num2, Middle>::result >::result) < (0),
           typename DivideBinSearch<Num1, Num2, Left, Middle,
           typename DivideByShort<typename Add<Left, Middle>::result,
           2>::result >::result,
           typename DivideBinSearch<Num1, Num2, Middle, Right,
           typename DivideByShort<typename Add<Middle, Right>::result,
           2>::result >::result >::result result;
};

template<typename Num1, typename Num2, typename Left, typename Right>
struct DivideBinSearch<Num1, Num2, Left, Right, Left>
{
   typedef Left result;
};

template<typename Num1, typename Num2>
struct Divide_
{
   typedef typename CutZeroes<typename DivideBinSearch<Num1, Num2,
           EmptyList, Num1,
           typename DivideByShort<Num1, 2>::result >::result >::result result;
};

template<typename Num1, typename Num2>
struct Divide
{
   typedef typename MetaIf<Length<typename Divide_<Num1,
           Num2>::result >::length == 0,
           List<0, EmptyList>,
           typename Divide_<Num1, Num2>::result >::result result;
};

#endif

